/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2024-05-03
 * Time: 18:26
 */
//1035.不相交的线
class Solution2 {
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int n = nums1.length, m = nums2.length;

        //1.创建dp表
        //dp[i][j]表示nums1的区间[0,i]子序列和nums2的区间[0,j]子序列的最大公共子序列长度
        int[][] dp = new int[n+1][m+1];
        //2.初始化
        //3.状态转移
        //4.遍历顺序
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                if(nums1[i-1] == nums2[j-1]) {
                    dp[i][j] = dp[i-1][j-1]+1;
                }else {
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        //5.返回值
        return dp[n][m];
    }
}
